"""
bfs
"""


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return "[]"

        queue = collections.deque()
        queue.append(root)
        res = []

        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.popleft()

                if cur:
                    res.append(str(cur.val))
                else:
                    res.append("null")

                if cur:
                    queue.append(cur.left)
                if cur:
                    queue.append(cur.right)

        return "[" + ','.join(res) + "]"

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        res = data[1:-1]
        # 特殊情况[""]
        if not res:
            return None
        # 其中还是字符串
        res = res.split(',')
        queue = collections.deque()
        root = TreeNode(int(res[0]))
        queue.append(root)
        i = 1  # 遍历res
        n = len(res)

        while i < n and queue:
            size = len(queue)

            for _ in range(size):
                cur = queue.popleft()

                # 我们不会创建一个空节点，所以不需要处理当前节点

                # 我们看下一个节点是否存在
                if i < n and res[i] == "null":
                    i += 1
                else:
                    # 创建节点，并入队
                    cur.left = TreeNode(int(res[i]))
                    queue.append(cur.left)
                    i += 1

                if i < n and res[i] == "null":
                    i += 1
                else:
                    cur.right = TreeNode(int(res[i]))
                    queue.append(cur.right)
                    i += 1
        return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if data == "[]":
            return None

        data = data[1:-1].split(',')

        queue = collections.deque()
        root = TreeNode(int(data[0]))
        queue.append(root)
        i = 0
        n = len(data)

        while queue and i < n:
            size = len(queue)
            for index in range(size):
                cur = queue.popleft()

                if data[i + 1] != "null":
                    left = TreeNode(int(data[i + 1]))
                    queue.append(left)
                    cur.left = left
                    i += 1
                else:
                    i += 1

                if data[i + 1] != "null":
                    right = TreeNode(int(data[i + 1]))
                    queue.append(right)
                    cur.right = right
                    i += 1
                else:
                    i += 1
        return root


import collections

class Codec:
    
    def __init__(self):
        self.seq = ","
        self.NULL = "null"
        
    
    def serialize(self, root):
        """
        1. 特殊情况，树为空
        2. 初始化空字符串，空队列并把根节点root加入队列
        3. 利用层序遍历的框架,当队列不为空
            4. 如果当前节点为空，加入字符串null,并进入下一次循环
            5. 如果当前节点不为空，则加入当前节点cur.val
            6. 不论左右子树是否为空，直接加入队列
        7. 返回结果
        """
        if root is None:
            return ""
        
        serialize_string = ""
        queue = collections.deque()
        queue.append(root)

        while queue:
            cur = queue.popleft()

            if cur is None:
                serialize_string += self.NULL + self.seq
                continue

            serialize_string += str(cur.val) + self.seq

            queue.append(cur.left)
            queue.append(cur.right)
        
        return "[" + serialize_string[:-1] + "]"
    
    def deserialize(self, data):
        """
        1. 特殊情况，输入字符串为空，返回空节点
        2. 将字符串进行分割，
        3. 分割后列表第一个数就是root.val, 创建根节点
        4. 根节点进入队列
        5. 根据队列的长度进行遍历 for 
            6. 将父节点从queue中取出parent，
            7. 将左节点从列表中取出，并对i++
            8. 如果左子节点不为空，创建节点并作为parent的左子树；同时加入到队列
                如果为空，parent的左子树悬空
            9. 将右节点从列表中取出，并对i++ 
            10. 如果右子节点为空，创建节点并作为parent的右子树；同时加入到队列
                如果为空，parent的右子树悬空
        11. 返回根节点
        """
        
        
        node_str = data[1:-1]
        if not node_str:
            return None
        node_list = node_str.split(',')
  
        root = TreeNode(int(node_list[0]))
        queue = collections.deque()
        queue.append(root)
        i = 1
        n = len(node_list)

        while i < n and queue:
           
            parent = queue.popleft()
            
            left_node = (node_list[i])
            i += 1
            if left_node == "null":
                parent.left = None
            else:
                parent.left = TreeNode(int(left_node))
                queue.append(parent.left)
            
            right_node = (node_list[i])
            i += 1
            if right_node == "null":
                parent.right = None
            else:
                parent.right = TreeNode(int(right_node))
                queue.append(parent.right)
            
        return root